House Robber

Try to solve the House Robber problem.

Statement#

As a skilled thief, you are planning to rob multiple houses on a street, each of which contains a substantial amount of money. However, you cannot rob the adjacent houses due to the connected security systems. Otherwise, the police will be contacted automatically.

Given an array of integers, nums, representing the amount of money present in each house, return the maximum amount of money that you can successfully steal without notifying the police.

Constraints

  • 1≤1 \leq nums.length ≤900\leq 900
  • 0≤0 \leq nums[i] ≤400\leq 400

Example#

Created with Fabric.js 3.6.6

1 of 6

Created with Fabric.js 3.6.6

2 of 6

Created with Fabric.js 3.6.6

3 of 6

Created with Fabric.js 3.6.6

4 of 6

Created with Fabric.js 3.6.6

5 of 6

Created with Fabric.js 3.6.6

6 of 6

Understand the problem#

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

House Robber

3

Given the following array, nums, what would be the correct output?

nums = [1, 8, 3, 4, 9, 2, 6]

Your Answer
A)

19

Correct Answer
B)

23

Explanation

Rob house 2 (money = 8), house 5 (money = 9), and house 7 (money = 6).

Total amount you can rob = 8 + 9 + 6 = 23.

C)

14

D)

18

Question 3 of 33 attempted

Try it yourself#

Implement your solution in the following coding playground:

The optimal solution to this problem runs in O(n) time and takes O(1) space.

Python
usercode > main.py
Powered by AI
Input #1
House Robber

You might want to go over the Dynamic Programming pattern again.

Lemonade Change

Find All Numbers Disappeared in an Array